/*************************************************************************
> File Name: counting_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-22 09:38:45
> Description: 计数排序（非常鸡肋）只能排非负数 需要知道最大值
************************************************************************/
#define MAX 100

#include "general.h"
#include <stdio.h>

void countingSort(int arr[], int length);
int main(int argc, char const *argv[])
{
    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    countingSort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
    return 0;
}

void countingSort(int arr[], int length)
{
    int max = getArrMax(arr, length);
    if (max > MAX)
    {
        return;
    }
    int counting[MAX] = {0};
    int i = 0, j = 0;

    for (i = 0; i < length; i++)
    {
        counting[arr[i]]++;
    }
    i = 0;
    for (; i < MAX; i++)
    {
        while (counting[i] > 0)
        {
            arr[j] = i;
            counting[i]--;
            j++;
        }
    }
}